Applicants' invention relates to apparatus and methods for communicating information securely, which is to say with reduced susceptibility to eavesdropping, through communication links, such as telephone lines, that have either non-reciprocal or reciprocal characteristics.
The widespread need for secure communication systems is apparent. As just one example, financial transactions are routinely conducted through telephone lines. In this and many other examples, it is critical that the communications of information are conducted with almost perfect secrecy, despite potential eavesdroppers' having access to strong information signals.
One way of providing security is to encrypt the communicated information according to some system that the users have agreed in advance to use. Several encryption methods have been described in the literature, such as the data encryption standard (DES) and public key cryptography (PKC). As explained in W. Diffie et al., "Privacy and Authentication: An Introduction to Cryptography", Proc. IEEE vol. 67, pp. 397-427 (March 1979), a classical cryptographic system is in general a set of instructions, a piece of hardware, or a computer program that can convert plaintext (unencrypted information) to ciphertext, or vice versa, in a variety of ways, one of which is selected by a specific key that is known to the users but is kept secret from others. The DES is a classical cryptographic system.
Popular PKC systems make use of the fact that finding large prime numbers is computationally easy but factoring the products of two large prime numbers is computationally difficult. PKC systems have an advantage over other cryptographic systems like the DES in that a PKC system uses a key for decryption that is different from the key for encryption. Thus, a PKC user's encryption key can be published for use by others, and the difficulty of securely distributing keys is avoided. See, e.g., R. I. Rivest et al., "A Method of Obtaining Digital Signatures and Public-Key Cryptosystems", Commun, of the ACM vol. 21, pp. 120-126 (February 1978); and W. Diffie, "The First Ten Years of Public-Key Cryptography", Proc. IEEE vol. 76, pp. 560-577 (May 1988).
For either a classical or PKC system, the security of a message is dependent to a great extent on the length of the key, as described in C. E. Shannon, "Communication Theory of Secrecy Systems", Bell Sys. Tech. J. vol. 28, pp. 656-715 (October 1949).
Unfortunately, it is often the case that two users (two police officers, for instance) have not agreed in advance to share a secret key. This makes secure real-time communication impossible via a classical cryptographic system and even via a PKC system, which requires a user to generate a pseudo-random quantity. Moreover, popular PKC systems are unprovably secure, and suffer from severe requirements in computational complexity and amount of information that must be exchanged. As new ways of attacking PKC systems are mounted, PKC systems will retreat to ever longer exchange vectors (in effect, larger prime numbers) and ever more complex computations. As a result, classical and PKC cryptographic systems are less than ideal for many communication situations.
Besides providing for security, much effort is expended to overcome the inevitable transmission errors that afflict communication systems, errors that can have dire consequences in a digital communication system. One way of dealing with such errors is to use error-correction codes that reduce the probability of bit errors at the receiver. For example, analog information to be transmitted is converted into digital information, which is then transformed according to a block error-correction code. As pointed out in D. Calcutt et al., Satellite Communications Principles and Applications pp. 136-161, the process of coding packages the bits that contain information to be transmitted with other bits, sometimes called "redundant bits" because they contain no information, that can assist in the detection and correction of errors.
Many modern digital communication systems employ such error-correction schemes, including such cellular radio systems as the North American digital advanced mobile phone service (D-AMPS), some of the characteristics of which are specified by the IS-54-B and IS-136 standards published by the Electronic Industries Association and Telecommunications Industry Association (EIA/TIA), and the European GSM system.
In such time-division multiple access (TDMA) systems, each radio channel, or radio carrier frequency, is divided into a series of time slots, each of which contains a burst of information from a data source, e.g., a digitally encoded portion of a voice conversation. During each time slot, 324 bits may be transmitted, of which the major portion, 260 bits, is due to the speech output of a coder/decoder (codec), including bits due to error-correction coding of the speech output. The remaining bits are used for guard times and overhead signaling for purposes such as synchronization. Control information is sent in a similar way. Time slot formats on a digital control channel according to the IS-136 standard are substantially the same as the formats used for digital traffic channels under the IS-54-B standard, but new functionalities are accorded to the fields in each slot in accordance with U.S. patent application Ser. No. 08/331,703 filed Oct. 31, 1994.
Other approaches to communication use systems called code division multiplexing (CDM) and code division multiple access (CDMA). In a conventional CDMA system, a digital information sequence to be communicated is spread, or mapped, into a longer digital sequence by combining the information sequence with a spreading sequence. As a result, one or more bits of the information sequence are represented by a sequence of N "chip" values. In one form of this process, called "direct spreading", each spread symbol is essentially the product of an information symbol and the spreading sequence. In a second form of spreading called "indirect spreading", the different possible information symbols are replaced by different, not necessarily related, spreading sequences. It will be understood that the information symbols may be produced by preceding stages of channel coding and/or spreading. Various aspects of conventional CDMA communications are described in K. Gilhousen et al., "On the Capacity of a Cellular CDMA System," IEEE Trans. Veh. Technol. vol. 40, pp. 303-312 (May 1991); and the following U.S. patent documents: U.S. Pat. No. 5,151,919 to Dent; and U.S. Pat. No. 5,353,352 to Dent et al.; and U.S. patent application Ser. No. 08/155,557 filed Nov. 22, 1993.